A portion of the disclosure of this document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction of the patent document or the patent disclosure as it appears in the Patent and Trademark Office files or records, but otherwise reserves all copyrights whatsoever.
The present invention relates generally to data communication and storage. More specifically, systems and methods are disclosed for integrating the protection of data secrecy with the protection of data integrity.
In secure communication and storage applications, it is often desirable to protect both the secrecy and the integrity of information in order to ensure that neither unauthorized disclosure nor undetected modification occurs. For example, if the integrity of an electronic communication is protected, but not its secrecy, an attacker can intercept the communication and make free use of the information contained therein. Similarly, if the secrecy of a communication is protected, but not its integrity, an attacker can intercept the communication and alter it in a way that subverts the purpose of the communication. For example, if the communication consists of an encrypted software program, an attacker could intercept the ciphertext version of the program during transmission and modify it in a way that causes it to fail or to perform unwanted or malicious operations. Without a way to detect such modifications, the recipient (and the sender) will be unable to prevent execution of the corrupted program, and the recipient may attribute the faulty or malicious behavior of the program to poor workmanship or malicious intent on the part of the author or distributor. One of ordinary skill in the art will appreciate that there are other situations in which it is advantageous to preserve both the secrecy and the integrity of a communication.
Conventional techniques typically use two independent mechanisms to provide secrecy and authentication. For example, an encryption algorithm may be used to protect secrecy, and a separate cryptographic checksum or message authentication code may be used to detect modifications. A commonly employed solution is to use the Data Encryption Standard (DES) algorithm in Cipher Block Chaining (CBC) mode for secrecy protection, and a DES-CBC Message Authentication Code (MAC) to provide integrity protection or validation, using different cryptographic keys for each process to prevent straightforward attacks on the DES-CBC MAC.
FIGS. 1A and 1B illustrate this conventional approach. Referring to FIG. 1A, the sender of a message encrypts the plaintext form of the message 10 using encryption function 12. In addition, the sender generates a message authentication code (MAC) 16 by applying MAC function 18 to plaintext 10. The sender combines MAC 16 with ciphertext 14, and sends the result 15 to the recipient. As shown in FIG. 1B, upon receipt of message 15xe2x80x2 (i.e., message 15 after transmission), the recipient must first decrypt the ciphertext using decryption function 20. Decryption function 20 yields a plaintext representation of the message 22, which the recipient checks for authenticity by computing a MAC 24. MAC 24 is compared to MAC 16xe2x80x2 (i.e., the received version of MAC 16) attached to ciphertext message 15xe2x80x2. If MAC 24 is equal to MAC 16xe2x80x2, then the message is deemed to be valid.
This conventional approach has significant disadvantages, however, as it typically requires that two algorithms (i.e., one for secrecy and one for authentication) be implemented in the system, and that the protected data be processed twice. In addition, as FIGS. 1A and 1B illustrate, the conventional process requires that these two processing passes be performed by both the sender and the recipient. Moreover, even if the same basic algorithm is used for both functions, storage is still required for the runtime state of two instances of the algorithm, and twice the processing resources, as well as two different cryptographic keys in some implementations, are required to perform both functions.
A related approach is to use a cryptographic hash function, such as the Secure Hash Algorithm version 1 (i.e., SHA-1), to append a secure manipulation detection code (MDC) to the plaintext, and then to encrypt the plaintext and the MDC for secrecy protection using a block cipher such as DES. This approach is illustrated in FIGS. 2A and 2B, which show the operations performed at the message source and at the message destination, respectively. The techniques shown in FIGS. 2A and 2B are used in the Internet Protocol Security Extensions (IPSEC), and have a processing time advantage over the techniques shown in FIGS. 1A and 1B, since cryptographic hash functions are typically faster than block ciphers of similar strength. However, although this approach is faster, it can require more code space (or hardware), since it employs two distinct algorithms.
Various approaches have been suggested for eliminating the extra processing burden and the extra algorithmic cost associated with the techniques described above. For example, the error propagation properties of some modes of operation appear to provide a degree of integrity protection (validation). One such approach, Propagating Cipher Block Chaining (PCBC), was specifically designed to ensure that any manipulation of the ciphertext would damage all subsequent ciphertext. However, PCBC, like other attempts to achieve similar results, is vulnerable to relatively straightforward attacks. For example, with respect to PCBC, swapping two ciphertext blocks leaves the rest of the message unchanged.
Thus, there is a need for systems and methods that protect the secrecy and integrity of a message without consuming the time, memory, or processing resources associated with conventional approaches. In addition, there is a need for systems and methods that can provide these efficiencies without decreasing the level of security substantially below that which is offered by the conventional approaches.
The present invention provides systems and methods for efficiently protecting the integrity and the secrecy of data by integrating the integrity protection function with the internal operation of an encryption and decryption algorithm. It should be appreciated that the present invention can be implemented in numerous ways, including as a process, an apparatus, a system, a device, a method, or a computer readable medium such as a computer readable storage medium or a computer network wherein program instructions are sent over optical or electronic communication lines. Several inventive embodiments of the present invention are described below.
In one embodiment, a method for processing data in a manner designed to protect the data""s secrecy and integrity is disclosed. The data are encrypted, and a validation code is generated for later use in detecting modification to the encrypted data. The encrypted data and the validation code are then transmitted to another system or to a storage device. There, the encrypted data can be retrieved and decrypted as part of an integrated process that is operable to decrypt the encrypted data and to yield a validation code. This validation code can be compared to the original validation code. If the two validation codes are not equal, this serves as an indication that the encrypted data or the original validation code was modified after the data was encrypted.
In another embodiment, a system for processing data is disclosed. The system includes a processor, a memory unit, logic for encrypting a data file, logic for decrypting the encrypted data file, and logic for receiving internal intermediate states from the decryption logic, and for using the internal intermediate state values to generate a validation code. The system may also include a mixing function for combining internal intermediate state values with an input validation value to yield an output validation value that can be used in the generation of the validation code. The mixing function can include an adder for adding a portion of the input validation value to one of the internal intermediate state values, a first shift register for shifting the adder""s output by a predefined number of bits, logical exclusive-or circuitry for performing an exclusive-or operation on another portion of the input validation value and another of the internal intermediate state values, a second shift register for shifting exclusive-or circuitry""s output by a predefined number of bits, and circuitry for concatenating the output from the shift registers to form an output validation value. The output validation value can be sent, along with the encrypted data, to another system or a storage device.
In yet another embodiment, a system is described for retrieving encrypted data and a validation code, and for using the validation code to check the authenticity of the encrypted data. The system includes a processing unit, a memory unit containing an encrypted file and a first validation code, decryption logic for decrypting the encrypted file, and logic for accepting a first and second intermediate state values from the decryption logic, and for using the intermediate state values to generate a second validation code. The logic for using the intermediate state values to generate a second validation code includes an adder for adding a first portion of an input validation value to the first intermediate state. The logic also includes a first shift register for shifting an output from the adder by a first predefined number of bits, the predefined number of bits being derived, at least in part, from the second intermediate state. In addition, the logic includes circuitry for calculating the logical exclusive-or of a second portion of the input validation value and the second intermediate value. The system further includes a second shift register for shifting an output from the logical exclusive-or circuitry by a second predefined number of bits, the second predefined number of bits being derived, at least in part, from the first intermediate state. Circuitry for concatenating an output from the first shift register with an output from the second shift register to form an output validation value is also included.
These and other features and advantages of the present invention will be presented in more detail in the following detailed description and the accompanying figures which illustrate by way of example the principles of the invention.